In H.264/AVC, macroblocks (MBs) in one frame are coded in raster scan order from one starting macroblock in left-up position. Each MB is coded one by one serially, no matter what the rate-distortion (R-D) cost of the coded MB is. FIG. 1 shows the raster scan order that H.264/AVC uses to implement intra prediction. The macroblock with bold font is the starting macroblock in H.264/AVC. There is only one starting MB per image.
Having multi-core processing architectures available, it is desirable to improve the parallelism of the intra prediction algorithm used in H.264/AVC, and to find the optimal prediction path of a video frame so as to improve the coding and compression performance for intra frames.